package com.al.demo;

public class Demo2 {
	
	public static void main(String[] args) {
		int[] arr = new int[] {2,6,9,13,25,45,85};
		System.out.println(search(arr,45,0,6));
		System.out.println(search(arr,45));
	}
	
	
	public static int search(int[] arr,int key, int low,int high) {
		if(key < arr[low] || key > arr[high] || arr[low] > arr[high]) {
			return -1;
		}
		int middle = (low + high) / 2;
		if(arr[middle] > key) {
			return search(arr, key, low, middle -1);
		}else if(arr[middle] < key) {
			return search(arr, key, middle + 1, high);
		}else {
			return middle;
		}
	}
	public static int search(int[] arr, int key) {
		int left = 0;
		int right = arr.length - 1;
		if(left > right) {
			return -1;
		}
		while(left <= right) {
			int middle = (left + right) >> 1;
			if(arr[middle] == key) {
				return middle;
			}else if(arr[middle] > key) {
				right = middle - 1;
			}else {
				left = middle + 1;
			}
		}
		return -1;
	}

}
